package william.backtracing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/3/25
 * @description <a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/">...</a>
 */
public class Leetcode17_电话号码的字母组合 {
    /**
     * 使用静态常量,维护数字->字母字符串的映射关系
     */
    private static final String[] DIGIT_TO_LETTER = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    /**
     * 使用成员变量保存结果
     */
    private List<String> result = new ArrayList<>();

    /**
     * 采用递归算法实现
     * 使用一个全局数组,维护数字->字母字符串的映射关系
     * 定义递归函数findLetterCombinations:
     * 对于字符串digits[i,N]范围的字符串组合,等价于digits[i]+digits[i+1,N]范围的字符串组合
     * 而digits[i]就对应映射表中的字母字符串
     */
    public List<String> letterCombinations(String digits) {
        //边界条件校验
        if (digits == null || digits.isEmpty()) {
            return Collections.emptyList();
        }

        //调用递归实现
        findLetterCombinations(digits, 0, "");

        //返回结果
        return result;
    }

    /**
     * 递归实现
     * 对于数字字符串digits中索引为idx位置的字符,生成字母组合,追加到prefix前缀后面
     */
    private void findLetterCombinations(String digits, int idx, String prefix) {
        //递归终止条件:整个数字字符串digits已经处理完成,保存结果
        if (idx == digits.length()) {
            result.add(prefix);
            return;
        }

        //递归处理:在prefix后面追加当前数字对应的字母字符串的组合
        String letters = DIGIT_TO_LETTER[digits.charAt(idx++) - '1'];
        for (int i = 0; i < letters.length(); i++) {
            findLetterCombinations(digits, idx, prefix + letters.charAt(i));
        }
    }
}
